package com.cn.algorithm02.class14;

import java.util.*;

/***
 * @author: hels
 * @description: 多叉树问题
 * 多叉树表示公司的组织结构，每个节点都有快乐值（value），邀请同事参加聚会，
 * ①可以随便选节点
 * ②选择节点的上下级不能选
 * ③最终的快乐值是最大的
 **/
public class C04_MaxHappy {
    public static class Employee {
        public int value;
        public List<Employee> nexts;

        public Employee(int value) {
            this.value = value;
            this.nexts = new ArrayList<>();
        }


        public String toString2() {
            String str = "[";
            if (nexts != null || nexts.size() > 0) {
                for (Employee e : nexts) {
                    str = str + "EPE{value="+ e.value + "},";
                }
            }

            return "Employee{" +
                    "value=" + value +
                    ", nexts=" + str.substring(0, str.length()-1) +
                    "]}";
        }

        @Override
        public String toString() {
            return "Employee{" +
                    "value=" + value +
                    ", nexts=" + nexts +
                    '}';
        }
    }

    public static void printData(Employee head) {
        Queue<Employee> queue = new LinkedList<>();
        queue.add(head);
        Employee x = null;
        while (!queue.isEmpty()) {
           x = queue.poll();
            System.out.println(x.toString2());
           if (x.nexts != null && x.nexts.size() > 0) {
               for (Employee e : x.nexts) {
                   queue.add(e);
               }
           }
        }
    }

    public static void main(String[] args) {
        Employee head = genarateBoss(3, 3, 9);
        printData(head);
        System.out.println("==========");
        maxHappy(head);

    }

    public static Info maxHappy(Employee head) {
        Info info = process(head);
        System.out.println("yes: " + info.yes);
        System.out.println("no:  " + info.no);
        return info;
    }

    public static class Info {
        public int yes;
        public int no ;

        public Info(int yes, int no) {
            this.yes = yes;
            this.no = no;
        }
    }

    public static Info process(Employee x) {
        if (x == null) return new Info(0, 0);

        int yes = x.value;
        int no = 0;
        for (Employee e: x.nexts) {
            Info nextInfo = process(e);
            yes += nextInfo.no;
            no += Math.max(nextInfo.no, nextInfo.yes);
        }
        return new Info(yes, no);
    }


    // for test
    public static Employee genarateBoss(int maxLevel, int maxNexts, int maxHappy) {
        /*if (Math.random() < 0.02) {
            return null;
        }*/
        Employee boss = new Employee((int) (Math.random() * (maxHappy + 1)));
        genarateNexts(boss, 1, maxLevel, maxNexts, maxHappy);
        return boss;
    }

    // for test
    public static void genarateNexts(Employee e, int level, int maxLevel, int maxNexts, int maxHappy) {
        if (level > maxLevel) {
            return;
        }
        int nextsSize = (int) (Math.random() * (maxNexts + 1));
        for (int i = 0; i < nextsSize; i++) {
            Employee next = new Employee((int) (Math.random() * (maxHappy + 1)));
            e.nexts.add(next);
            genarateNexts(next, level + 1, maxLevel, maxNexts, maxHappy);
        }
    }
}
